// 9-21 求后缀表达式
// 先求后缀表达式 再根据后缀表达式求值
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 100

int rank(char a, char b)
{
    if (b == '(')
        return 1;
    if ((a == '*' || a == '/') && (b == '+' || b == '-'))
        return 1;
    return 0;
}
char *operation(char *s)
{
    if (!s || s[0] == '\0')
        return 0;
    char s2[MAX];
    char *s1 = (char *)malloc(MAX);
    int top1 = -1, top2 = -1;
    for (int i = 0; s[i]; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            s1[++top1] = s[i];
        }
        else
        {
            // isempty
            if (top2 < 0 || s[i] == '(')
                s2[++top2] = s[i];
            else
            {
                if (s[i] == ')')
                {
                    while (top2 >= 0 && s2[top2] != '(')
                        s1[++top1] = s2[top2--];

                    top2--;
                }
                else
                {
                    while (top2 >= 0 && rank(s[i], s2[top2]) == 0)
                    {
                        s1[++top1] = s2[top2--];
                    }
                    s2[++top2] = s[i];
                }
            }
        }
    }
    while (top2 >= 0)
    {
        s1[++top1] = s2[top2--];
    }
    s1[++top1] = '\0';
    printf("%s ", s1);
    return s1;
}
int caculat(char *s)
{
    if (!s)
        return 0;
    int stack[MAX], top = -1;
    for (int i = 0; s[i]; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
            stack[++top] = s[i] - '0';
        else
        {
            if (top < 1)
                return 0;
            int b = stack[top--];
            int a = stack[top--];
            switch (s[i])
            {
            case '+':
                stack[++top] = a + b;
                break;
            case '-':
                stack[++top] = a - b;
                break;
            case '*':
                stack[++top] = a * b;
                break;
            case '/':
                stack[++top] = a / b;
                break;
            default:
                break;
            }
        }
    }
    printf("\n%d", stack[0]);
    return stack[0];
}

int main()
{
    /*******************code*******************/
    char *s = "1+((2+3)*4)-5";
    char *s1 = operation(s);
    caculat(s1);

    /******************************************/
    fflush(stdin);

    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
